<html>
<head>
	<title>binarytree</title>
</head>
<body>
	你好，这里是使用js实现的排序二叉树的小demo，参考网上的知识汇聚而成，仅供参考。
	<br>
	使用Chrome,点击F12打开开发者工具

	<script>
	
		// 排序二叉树 类
		function BinaryTree(){
			//节点
			var Node = function (key){
				this.key = key;
				this.left = null;
				this.right = null;
			}

			//根节点
			var root = null;

			//排序二叉树 插入节点
			var insertNode = function(node,newNode){
				if(newNode.key < node.key){
					if(node.left === null){
						node.left = newNode;
					}else{
						insertNode(node.left,newNode);
					}
				}else{
					if(node.right === null){
						node.right = newNode;
					}else{
						insertNode(node.right,newNode);
					}
				}
			}

			//创建排序二叉树
			this.insert = function(key){
				var newNode = new Node(key);
				if(root === null){
					root = newNode;
				}else{
					insertNode(root,newNode);	
				}
			}

			var callback = function(key){
				console.log(key);
			}

			// 二叉树中序遍历（左 中 右）
			var inOrderTraverseNode = function(node,callback){
				if(node !==null){
					inOrderTraverseNode(node.left,callback);
					callback(node.key);
					inOrderTraverseNode(node.right,callback);
				}
			}

			// 中序遍历（对排序二叉树进行中序遍历 得到有序的数列）
			this.inOrderTraverse = function(){
				inOrderTraverseNode(root,callback);
			}

			// 二叉树前序遍历 （中 左 右）
			var preOrderTraverseNode = function(node,callback){
				if(node !==null){
					callback(node.key);
					preOrderTraverseNode(node.left,callback);
					preOrderTraverseNode(node.right,callback);
				}

			}

			// 前序遍历（用于复制二叉树）
			this.preOrderTraverse = function(){
				preOrderTraverseNode(root,callback);
			}

			//二叉树后序遍历 （左 右 中）
			var postOrderTraverseNode = function(node,callback){
				if(node !==null){
					postOrderTraverseNode(node.left,callback);
					postOrderTraverseNode(node.right,callback);
					callback(node.key);
				}
			}

			// 后序遍历
			this.postOrderTraverse = function(){
				postOrderTraverseNode(root,callback);
			}

			// 树的高度
			var maxDepth = function(node)   
			{  
				if (node === null) return 0;  
				var lh = maxDepth(node.left);  
				var rh = maxDepth(node.right);  
				return lh > rh ? lh + 1 : rh + 1;  
			} 
			
			this.getHeight = function(){
				var hegiht = maxDepth(root);
				console.log("树的高度为：" + hegiht);
			}

			//最大值 和 最小值
			var minNode = function(node){
				if(node===null)
					return;
				if(node.left===null){
					return node;
				}
				else{
					return minNode(node.left);
				}
			}	

			var maxNode = function(node){
				if(node===null)
					return;
				if(node.right===null){
					return node;
				}
				else{
					return maxNode(node.right);
				}
			}

			this.getMaxAndMin = function(){
				var max = maxNode(root);
				var min = minNode(root);
				console.log("max key：" + max.key);
				console.log("min key：" + min.key);
			}

			var findMinNode = function(node){
				if(node){
					while(node && node.left){
						node = node.left;
					}
					return node;
				}
				return null;
			}

			var findMaxNode = function(node){
				if(node){
					while(node && node.right){
						node = node.right;
					}
					return node;
				}
				return null;
			}

			//查找
			var searchNode = function(node,key){
				if(node === null){
					return false;
				}
				
				if(node.key === key)
					return true;
				else if(key > node.key)
					return searchNode(node.right , key);
				else if(key < node.key)
					return searchNode(node.left , key);
			}

			this.search = function(key){
				if(searchNode(root,key))
					console.log(key + " is found");
				else 
					console.log(key + " is not found");
			}

			//删除节点
			var removeNode = function(node,key){
				if(node === null)
					return null;

				if(key < node.key){
					node.left = removeNode(node.left,key);
					return node;
				}else if(key > node.key){
					node.right = removeNode(node.right,key);
					return node;
				}else {
					//第一种情况：删除节点无子节点
					if(node.left===null && node.right===null){
						node=null;
						return node;
					}
					//第二种情况：删除节点只有右孩子
					if(node.left===null){
						node = node.right;
						return node;
					}
					//第三种情况：删除节点只有左孩子
					if(node.right===null){
						node = node.left;
						return node;
					}
					//第四种情况：删除节点有左孩子和右孩子
					if(node.left!==null && node.right!==null){
						//找到右子树的最小节点
						var mark = findMinNode(node.right);
						//更新
						node.key = mark.key;
						//删除右子树的最小节点
						node.right = removeNode(node.right,mark.key);
					}

				}
			}

			this.remove = function(key){
				return removeNode(root,key);
			}

		}


		//测试
		//创建排序二叉树
		var nodes = [89,34,98,122,3,10000,-9,877,0,555,76,888,6,889,1,2];
		var binaryTree = new BinaryTree();
		nodes.forEach(function(key){
			binaryTree.insert(key);
		});
		//前序遍历
		//binaryTree.preOrderTraverse();
		console.log("---------------------------");

		//中序遍历
		//binaryTree.inOrderTraverse();
		console.log("---------------------------");

		//后序遍历
		//binaryTree.postOrderTraverse();
		console.log("---------------------------");

		// 高度
		binaryTree.getHeight();

		//最大最小值
		binaryTree.getMaxAndMin();

		//查找
		binaryTree.search(3);
		binaryTree.search(4);
		binaryTree.search(5);
	</script>
</body>
</html>